#include <bits/stdc++.h>

using namespace std;

// 范围内的数字计数
// 给定一个在 0 到 9 之间的整数 d，和两个正整数 low 和 high 分别作为上下界
// 返回 d 在 low 和 high 之间的整数中出现的次数，包括边界 low 和 high
// 测试链接 : https://leetcode.cn/problems/digit-count-in-range/

class Solution 
{
public:
    int digitsCount(int d, int a, int b)
    {
        return count(b, d) - count(a - 1, d);
    }

    // 统计1~num范围上所有的数中，数码d出现了多少次
    // 注意是1~num范围，不是0~num范围
    int count(int num, int d)
    {
        int ans = 0;
        // left : 当前位左边的情况数
        // right : 当前位右边的情况数
        // 当前位的数字是cur
        for(long right = 1, tmp = num, left, cur; tmp != 0; right *= 10, tmp /= 10)
        {
            // 情况1：
            // d != 0
            // 1 ~ 30583 , d = 5
            // cur < d的情况
            // 个位cur=3 : 0000~3057 5
            // 个位上没有额外加
            //
            // cur > d的情况
            // 十位cur=8 : 000~304 5 0~9
            // 十位上额外加 : 305 5 0~9
            //
            // cur == d的情况
            // 百位cur=5 : 00~29 5 00~99
            // 百位上额外加 : 30 5 00~83
            // ...
            // 情况2：
            // d == 0
            // 1 ~ 30583 d = 0
            // cur > d的情况
            // 个位cur=3 : 0001~3057 0
            // 个位上额外加 : 3058 0
            //
            // cur > d的情况
            // 十位cur=8 : 001~304 0 0~9
            // 十位上额外加 : 305 0 0~9
            //
            // cur > d的情况
            // 百位cur=5 : 01~29 0 00~99
            // 百位上额外加 : 30 0 00~99
            //
            // cur == d的情况
            // 千位cur=0 : 1~2 0 000~099
            // 千位上额外加 : 3 0 000~583
            left = tmp / 10;
            cur = tmp % 10;
            if(d == 0) --left;
            ans += left * right;
            if(cur > d) ans += right;
            else if(cur == d) ans += num % right + 1;
        }
        return ans;
    }
};


class Solution 
{
public:
    int digitsCount(int d, int a, int b)
    {
        return count(b, d) - count(a - 1, d);
    }

    int count(int n, int digit)
    {
        auto s = to_string(n);
        int m = s.size(), dp[m][m];
        memset(dp, -1, sizeof(dp));
        /*
        cnt 表示前面填了多少个 digit
    
        is_limit 表示当前是否受到了 n 的约束。若为真，则第 i 为填入的
        数字至多为 s[i]，否则可以是 9，如果在受到约束的情况下填了 s[i]，
        那么后续填入的数字仍会受到 n 的约束。
    
        is_num 表示 i 前面的数位是否填了数字。若为假，则当前位可以跳过
        （不填数字），或者要填入的数字至少为 1；若为真，则要填入的数字
        可以从 0 开始。

        在本题中，因为 digit 可能是 0，因此要考虑前导零，所以 is_num 不可以省略
        */
        function<int(int, int, bool, bool)> f = [&](int i, int cnt, bool is_limit, bool is_num) -> int
        {
            // 需要判断是否数字是否合法
            if(i == m) return is_num ? cnt : 0;
            // 缓存命中
            if(!is_limit && is_num && dp[i][cnt] != -1) return dp[i][cnt];
            int ret = 0;
            if(!is_num) ret = f(i + 1, cnt, false, false);
            int up = is_limit ? s[i] - '0' : 9;
            for(int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d
            {
                ret += f(i + 1, cnt + (d == digit), is_limit && d == up, true);
            }
            if(!is_limit && is_num) dp[i][cnt] = ret;
            return ret;
        };

        return f(0, 0, true, false);
    }
};